package com.lwl.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lwl
 * @Description TODO
 * @date 2023/8/1 9:56
 */
public class Code40CombinationSum2 {
    @Test
    public void test() {
        List<List<Integer>> lists = combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        for (List<Integer> list : lists) {
            list.forEach(System.out::print);
            System.out.println();
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curList = new ArrayList<>();
        Arrays.sort(candidates);
        process(candidates, 0, target, res, curList, false);
        return res;
    }

    private void process(int[] candidates, int index, int rest, List<List<Integer>> res, List<Integer> curList, boolean isAddPre) {
        if (rest == 0) {
            res.add(new ArrayList<>(curList));
            return;
        }
        if (index >= candidates.length) {
            return;
        }
        if (index - 1 >= 0 && candidates[index] == candidates[index - 1] && !isAddPre) {
            process(candidates, index + 1, rest, res, curList, false);
            return;
        }
        if (rest - candidates[index] >= 0) {
            // 加上当前
            curList.add(candidates[index]);
            process(candidates, index + 1, rest - candidates[index], res, curList, true);
            curList.remove(curList.size() - 1);
        }
        // 不加当前
        process(candidates, index + 1, rest, res, curList, false);
    }
}
